class Solution
{
public:
    int shortestBridge(vector<vector<int>> &grid)
    {
        int n = grid.size();
        queue<vector<int>> q;
        queue<vector<int>> island1;
        bool foundFirst = false;
        for (int i = 0; i < n; ++i)
        {
            if (foundFirst)
            {
                break;
            }
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 1)
                {
                    q.push({i, j});
                    island1.push({i, j});
                    grid[i][j] = -1;
                    foundFirst = true;
                    break;
                }
            }
        }
        while (!q.empty())
        {
            int x = q.front()[0];
            int y = q.front()[1];
            q.pop();
            if (x > 0 && grid[x - 1][y] == 1)
            {
                q.push({x - 1, y});
                island1.push({x - 1, y});
                grid[x - 1][y] = -1;
            }
            if (x < n - 1 && grid[x + 1][y] == 1)
            {
                q.push({x + 1, y});
                island1.push({x + 1, y});
                grid[x + 1][y] = -1;
            }
            if (y > 0 && grid[x][y - 1] == 1)
            {
                q.push({x, y - 1});
                island1.push({x, y - 1});
                grid[x][y - 1] = -1;
            }
            if (y < n - 1 && grid[x][y + 1] == 1)
            {
                q.push({x, y + 1});
                island1.push({x, y + 1});
                grid[x][y + 1] = -1;
            }
        }

        q.swap(island1);
        int step = 0;
        while (!q.empty())
        {
            int aroundSize = q.size();
            for (int i = 0; i < aroundSize; ++i)
            {
                int x = q.front()[0];
                int y = q.front()[1];
                q.pop();
                if (x > 0)
                {
                    if (grid[x - 1][y] == 1)
                    {
                        return step;
                    }
                    else if (grid[x - 1][y] != -1)
                    {
                        q.push({x - 1, y});
                        grid[x - 1][y] = -1;
                    }
                }
                if (x < n - 1)
                {
                    if (grid[x + 1][y] == 1)
                    {
                        return step;
                    }
                    else if (grid[x + 1][y] != -1)
                    {
                        q.push({x + 1, y});
                        grid[x + 1][y] = -1;
                    }
                }
                if (y > 0)
                {
                    if (grid[x][y - 1] == 1)
                    {
                        return step;
                    }
                    else if (grid[x][y - 1] != -1)
                    {
                        q.push({x, y - 1});
                        grid[x][y - 1] = -1;
                    }
                }
                if (y < n - 1)
                {
                    if (grid[x][y + 1] == 1)
                    {
                        return step;
                    }
                    else if (grid[x][y + 1] != -1)
                    {
                        q.push({x, y + 1});
                        grid[x][y + 1] = -1;
                    }
                }
            }
            ++step;
        }
        return -1;
    }
};